﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using MazeRunner.GameLogic;

namespace MazeRunner.GameState
{
	public static class MazeCreator
	{
		public static Maze CreateHardMaze(int width, int height, int roomCount, int roomMeanSize, int roomStdDev, int hallMeanSize, int hallStdDev, int pointCount, Random r)
		{
			Maze maze = new Maze(width, height, pointCount);

			MazeItem[,] mazeItems = maze.MazeItems;

			List<Point> _open = new List<Point>();
			HashSet<Point> _closed = new HashSet<Point>();

			// Start with a random point
			int startX = r.Next(2, width - 2);
			int startY = r.Next(2, height - 2);
			_open.Add(new Point(startX, startY));

			while (_open.Count > 0)
			{
				int currentIndex = r.Next(_open.Count);
				Point current = _open[currentIndex];

				// Check to see if this is a valid point
				if (!IsPointValid(mazeItems, current, _closed))
				{
					FastRemoveAt(currentIndex, _open);
					continue;
				}

				// The point is valid, so make it empty
				mazeItems[current.X, current.Y] = MazeItem.Empty;

				// We no longer want to deal with this one so add it to closed
				_closed.Add(current);
				FastRemoveAt(currentIndex, _open);

				// Add all adjacent points that aren't in closed
				Point point = new Point(current.X - 1, current.Y);
				if (IsPointValid(mazeItems, point, _closed))
				{
					_open.Add(point);
				}
				point = new Point(current.X + 1, current.Y);
				if (IsPointValid(mazeItems, point, _closed))
				{
					_open.Add(point);
				}
				point = new Point(current.X, current.Y - 1);
				if (IsPointValid(mazeItems, point, _closed))
				{
					_open.Add(point);
				}
				point = new Point(current.X, current.Y + 1);
				if (IsPointValid(mazeItems, point, _closed))
				{
					_open.Add(point);
				}
			}

			return maze;
		}

		public static Maze CreateRandomMaze(int width, int height, int roomCount, int roomMeanSize, int roomStdDev, int hallMeanSize, int hallStdDev, int pointCount, Random r)
		{
			Maze maze = new Maze(width, height, pointCount);

			List<Point> centers = CreateRooms(r, maze, width, height, roomCount, roomMeanSize, roomStdDev);
			CreateHalls(r, maze, centers, hallMeanSize, hallStdDev);
			return maze;
		}

		private static List<Point> CreateRooms(Random r, Maze maze, int width, int height, int roomCount, int roomMeanSize, int roomStdDev)
		{
			MazeItem[,] mazeItems = maze.MazeItems;

			// Get the number of rooms that will be created
			List<Point> centers = new List<Point>(roomCount);

			// Try to place the rooms
			int attempt = 0;
			for (int roomIndex = 0; roomIndex < roomCount; roomIndex++)
			{
				if (attempt > width)
				{
					// You've tried enough times but can't create a room - time to give up
					continue;
				}

				int roomLength = (int) (r.NextGaussian(roomMeanSize, roomStdDev) + 0.5);
				if (roomLength < 1)
				{
					// Bad room length - try again
					roomCount--;
					continue;
				}

				int roomLeft = r.Next(0, width - roomLength);
				int roomTop = r.Next(0, height - roomLength);

				// See if the position is valid
				bool valid = true;
				for (int i = -1; i < roomLength + 2; i++)
				{
					for (int j = -1; j < roomLength + 2; j++)
					{
						int posX = roomLeft + i;
						int posY = roomTop + j;
						if (posX < 0 || posX >= width - 1 || posY < 0 || posY >= height - 1)
						{
							// Out of bounds
							valid = false;
							break;
						}
						if (mazeItems[posX, posY] != MazeItem.Wall)
						{
							// Trying to create on top of another room
							valid = false;
							break;
						}
					}

					if (!valid)
					{
						break;
					}
				}

				if (!valid)
				{
					// Try again
					roomIndex--;
					attempt++;
					continue;
				}

				// Room is in valid location, so place it
				for (int i = 0; i < roomLength; i++)
				{
					for (int j = 0; j < roomLength; j++)
					{
						mazeItems[roomLeft + i, roomTop + j] = MazeItem.Empty;
					}
				}

				// Add the center of the room to the list of centers
				centers.Add(new Point(roomLeft + roomLength / 2, roomTop + roomLength / 2));
			}

			return centers;
		}

		private static void CreateHalls(Random r, Maze maze, List<Point> centers, int hallMeanSize, int hallStdDev)
		{
			MazeItem[,] mazeItems = maze.MazeItems;

			List<Point> disconnectedNodes = new List<Point>(centers);

			List<Point> connectedNodes = new List<Point>(centers.Count);

			// Remove the first node
			int nodeIndex = r.Next(disconnectedNodes.Count);
			Point newNode = disconnectedNodes[nodeIndex];
			disconnectedNodes.RemoveAt(nodeIndex);

			while (disconnectedNodes.Count > 0)
			{
				connectedNodes.Add(newNode);

				// Grab the next node to combine
				nodeIndex = r.Next(disconnectedNodes.Count);
				newNode = disconnectedNodes[nodeIndex];

				// Combine it
				Point combinedNode = connectedNodes[r.Next(connectedNodes.Count)];

				int width = (int)(r.NextGaussian(hallMeanSize, hallStdDev));
				width = Utilities.Clamp(2, 5, width);

				// Create the vertical part of the hall
				for (int i = combinedNode.X - width / 2; i < combinedNode.X + width / 2; i++)
				{
					for (int j = Math.Min(combinedNode.Y, newNode.Y) - width / 2; j < Math.Max(combinedNode.Y, newNode.Y) + width / 2; j++)
					{
						mazeItems[i, j] = MazeItem.Empty;
					}
				}

				// Create the horizontal part of the hall
				for (int i = Math.Min(combinedNode.X, newNode.X) - width / 2; i < Math.Max(combinedNode.X, newNode.X) + width / 2; i++)
				{
					for (int j = newNode.Y - width / 2; j < newNode.Y + width / 2; j++)
					{
						mazeItems[i, j] = MazeItem.Empty;
					}
				}

				disconnectedNodes.RemoveAt(nodeIndex);
			}
		}

		public static Point FindSpawnLocationsAndOptimizeMaze(Maze maze, Random r)
		{
			MazeItem[,] mazeItems = maze.MazeItems;

			//Remove the unnecessary wall blocks
			for (int i = 0; i < maze.Width; i++)
			{
				for (int j = 0; j < maze.Height; j++)
				{
					if (mazeItems[i, j] == MazeItem.Wall)
					{
						if ((i == 0 || mazeItems[i - 1, j] == MazeItem.Wall || mazeItems[i - 1, j] == MazeItem.Null) &&
							(j == 0 || mazeItems[i, j - 1] == MazeItem.Wall || mazeItems[i, j - 1] == MazeItem.Null) &&
							(i == maze.Width - 1 || mazeItems[i + 1, j] == MazeItem.Wall || mazeItems[i + 1, j] == MazeItem.Null) &&
							(j == maze.Height - 1 || mazeItems[i, j + 1] == MazeItem.Wall || mazeItems[i, j + 1] == MazeItem.Null))
						{
							//This is surrounded on all sides by walls, so remove it.
							mazeItems[i, j] = MazeItem.Null;
						}
					}
				}
			}

			Point startingPoint = new Point(-1, -1);
			bool foundStartingPoint = false;
			for (int i = 0; i < maze.Width; i++)
			{
				for (int j = 0; j < maze.Height; j++)
				{
					if (mazeItems[i, j] == MazeItem.Empty)
					{
						foundStartingPoint = true;
						startingPoint = new Point(i, j);
						break;
					}
				}
				if (foundStartingPoint)
				{
					break;
				}
			}

			int[,] distanceGrid = InitializeDataGrid(maze);

			// Find one of the farthest points in the grid and set it as the starting point
			UpdateDistanceGrid(distanceGrid, startingPoint);
			startingPoint = GetFarthestPoint(distanceGrid, r);

			// Reinitialize the data grid using the new, farthest starting point
			List<Point> points = new List<Point>();
			distanceGrid = InitializeDataGrid(maze);
			points.Add(startingPoint);
			UpdateDistanceGrid(distanceGrid, points[points.Count - 1]);

			for (int i = 1; i < maze.PointCount; i++)
			{
				points.Add(GetFarthestPoint(distanceGrid, r));
				UpdateDistanceGrid(distanceGrid, points[points.Count - 1]);
			}

			foreach (Point point in points)
			{
				mazeItems[point.X, point.Y] = MazeItem.LocalMaxima;
			}

			return points[1]; //return the starting position for the player
		}

		private static int[,] InitializeDataGrid(Maze maze)
		{
			int[,] distanceGrid = new int[maze.Width, maze.Height];
			MazeItem[,] mazeItems = maze.MazeItems;

			for (int i = 0; i < maze.Width; i++)
			{
				for (int j = 0; j < maze.Height; j++)
				{
					if (mazeItems[i, j] == MazeItem.Wall)
					{
						distanceGrid[i, j] = int.MinValue;
					}
					else
					{
						distanceGrid[i, j] = int.MaxValue;
					}
				}
			}

			return distanceGrid;
		}

		private static void UpdateDistanceGrid(int[,] distanceGrid, Point start)
		{
			// Recursive part that sets the distance for each empty space
			RecursivePart(distanceGrid, start.X, start.Y, 0);
		}

		private static void RecursivePart(int[,] distanceGrid, int x, int y, int currentDistance)
		{
			// Make sure it's not out of bounds
			// It shouldn't ever get here unless it is an invalid maze
			if (x < 0 || x >= distanceGrid.GetLength(0)
				|| y < 0 || y >= distanceGrid.GetLength(1))
			{
				return;
			}

			// Make sure we aren't working on one that is already closer
			if (distanceGrid[x, y] <= currentDistance)
			{
				return;
			}

			// Set the value
			distanceGrid[x, y] = currentDistance;

			// Do the same thing to its neighbors
			RecursivePart(distanceGrid, x + 1, y, currentDistance + 1);
			RecursivePart(distanceGrid, x - 1, y, currentDistance + 1);
			RecursivePart(distanceGrid, x, y + 1, currentDistance + 1);
			RecursivePart(distanceGrid, x, y - 1, currentDistance + 1);
		}

		/// <summary>
		/// Returns the point that is farthest away from any of the selected points in the grid.
		/// If there are multiple points that are the same farthest distance, it randomly picks one.
		/// </summary>
		private static Point GetFarthestPoint(int[,] distanceGrid, Random r)
		{
			List<Point> farthestPoints = new List<Point>();
			int farthestDistance = int.MinValue;

			int width = distanceGrid.GetLength(0);
			int height = distanceGrid.GetLength(1);
			int currentDistance;
			for (int i = 0; i < width; i++)
			{
				for (int j = 0; j < height; j++)
				{
					currentDistance = distanceGrid[i, j];
					if (currentDistance > farthestDistance)
					{
						farthestDistance = currentDistance;
						farthestPoints.Clear();
						farthestPoints.Add(new Point(i, j));
					}
					else if (currentDistance == farthestDistance)
					{
						farthestPoints.Add(new Point(i, j));
					}
				}
			}

			// Return any one of them randomly
			return farthestPoints[r.Next(farthestPoints.Count)];
		}

		/// <summary>
		/// Fast way of removing from _open.
		/// </summary>
		/// <param name="index"></param>
		private static void FastRemoveAt(int index, List<Point> _open)
		{
			_open[index] = _open[_open.Count - 1];
			_open.RemoveAt(_open.Count - 1);
		}

		private static bool IsPointValid(MazeItem[,] mazeItems, Point point, HashSet<Point> _closed)
		{
			// Are we trying to add a point that has already been added
			if (_closed.Contains(point))
			{
				return false;
			}

			// Is this point on the edge of the grid
			if (point.X == 0 || point.X == mazeItems.GetLength(0) - 1
				|| point.Y == 0 || point.Y == mazeItems.GetLength(1) - 1)
			{
				// Add the point to closed so we don't have to check to see if it is no longer valid
				_closed.Add(point);
				return false;
			}

			// Check to see if any of the adjacent points have been added
			// If more than one has been added, it isn't valid
			int adjacentEmptyPointCount = 0;
			if (mazeItems[point.X - 1, point.Y] == MazeItem.Empty)
			{
				adjacentEmptyPointCount++;
			}
			if (mazeItems[point.X + 1, point.Y] == MazeItem.Empty)
			{
				adjacentEmptyPointCount++;
			}
			if (mazeItems[point.X, point.Y - 1] == MazeItem.Empty)
			{
				adjacentEmptyPointCount++;
			}
			if (mazeItems[point.X, point.Y + 1] == MazeItem.Empty)
			{
				adjacentEmptyPointCount++;
			}
			//if (_closed.Contains(new Point(point.X - 1, point.Y)))
			//{
			//    adjacentEmptyPointCount++;
			//}
			//if (_closed.Contains(new Point(point.X + 1, point.Y)))
			//{
			//    adjacentEmptyPointCount++;
			//}
			//if (_closed.Contains(new Point(point.X, point.Y - 1)))
			//{
			//    adjacentEmptyPointCount++;
			//}
			//if (_closed.Contains(new Point(point.X, point.Y + 1)))
			//{
			//    adjacentEmptyPointCount++;
			//}

			if (adjacentEmptyPointCount > 1)
			{
				// It would create a loop, which we aren't allowing, so add it to closed so we never have to check this again
				_closed.Add(point);
				return false;
			}

			return true;
		}
	}
}
